from math import inf


class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        a = [0] * 5  # 当前位置各个数字总数
        b = [inf] * 5  # 最后出现位置
        q1 = [[inf] * 4 for _ in range(25)]  # 每种组合（25）在所有奇偶状态（4）的最小值
        q2 = [[[] for _ in range(4)] for _ in range(25)]  # 各状态队列
        for i in range(25):
            q2[i][0].append([-1, 0])  # 两种数值都没有，0|0偶偶状态的差值边界
        ans = -inf
        for kv, v in enumerate(s):
            ai = ord(v) - ord("0")
            a[ai] += 1  # 更新当前数量
            b[ai] = kv
            for i in range(5):  # 遍历状态组合
                for j in range(5):  # 遍历状态组合
                    if i != j:
                        index, c = i * 5 + j, a[i] - a[j]
                        # 奇偶性相反的两个状态 - 奇偶性相同的两个状态
                        f2 = ((a[i] & 1) << 1) | (a[j] & 1)  # 当前状态
                        f1 = (((a[i] & 1) ^ 1) << 1) | (a[j] & 1)  # 目标状态
                        # 左侧边界进入候选最小值
                        while q2[index][f1] and q2[index][f1][0][0] < min(
                            b[j], b[i], kv - k + 1
                        ):
                            q1[index][f1] = min(q1[index][f1], q2[index][f1][0][1])
                            q2[index][f1].pop(0)
                        # 当前状态进入队列
                        q2[index][f2].append((kv, c))
                        # 更新答案
                        if a[i] > 0 and a[j] > 0:
                            ans = max(ans, c - q1[index][f1])
        return ans


class Solution:
    def maxDifference(self, s: str, k: int) -> int:
        a = [0] * 5  # 当前位置各个数字总数
        b = [inf] * 5  # 最后出现位置
        q1 = [[inf] * 4 for _ in range(25)]  # 每种组合（25）在所有奇偶状态（4）的最小值
        q2 = [[[] for _ in range(4)] for _ in range(25)]  # 各状态队列
        for i in range(25):
            q2[i][0].append([-1, 0])  # 两种数值都没有，0|0偶偶状态的差值边界
        ans = -inf
        for kv, v in enumerate(s):
            ai = ord(v) - ord("0")
            a[ai] += 1  # 更新当前数量
            b[ai] = kv
            for i in range(5):  # 遍历状态组合
                for j in range(5):  # 遍历状态组合
                    index, c = i * 5 + j, a[i] - a[j]
                    f2 = ((a[i] & 1) << 1) | (a[j] & 1)  # 当前状态
                    f1 = (((a[i] & 1) ^ 1) << 1) | (a[j] & 1)  # 目标状态
                    while q2[index][f1] and q2[index][f1][0][0] < min(
                        b[j], b[i], kv - k + 1
                    ):
                        q1[index][f1] = min(q1[index][f1], q2[index][f1][0][1])
                        q2[index][f1].pop(0)
                    q2[index][f2].append((kv, c))
                    if a[i] > 0 and a[j] > 0:
                        ans = max(ans, c - q1[index][f1])
        return ans


s = Solution()
print(s.maxDifference("2222130", 2) == -1)
# print(s.maxDifference("24112", 1) == -1)
# print(s.maxDifference("2421", 1))
# print(s.maxDifference(s="110", k=3))
# print(s.maxDifference("12233", 4))

# q1 = [[inf] * 4 for _ in range(25)]

# print(q1)

s = "012345"
print(s[1:3])
